import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

public class Sort {

    //插入排序
    /**
     * 时间复杂度：O(N^2) 倒序
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void insertSort(int[] array) {
        //从第二个元素开始处理
        for (int i = 1; i < array.length; i++) {
             int tmp = array[i];
             int j = i - 1;
             for(;j >= 0;j--) {
                 if(tmp < array[j]) {
                     //将比array[i]大的元素往后移
                     array[j + 1]  = array[j];
                 }else {
                     //找到了插入位置，结束循环
                     break;
                 }
             }

             //将array[i]插入指定的位置,思考：为什么是在j+1位置插入而不是j位置插入元素？
             array[j+1] = tmp;
        }
    }

    //希尔排序
    //先对数组中的元素进行分组，每个分组内的元素进行直接插入排序。设置一个间隔gap，初始时gap等于数组长度的一半，每次gap都减半
    public static void ShellSort(int[] array) {
        int gap = array.length / 2;
        while(gap >= 1) {
            Shell(array,gap);
            gap /= 2;
        }
    }

    private static void Shell(int[] array, int gap) {
        //记住直接插入排序是增量为1的希尔排序
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j-=gap ){
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }



    //对指定区间的插入排序

    /**
     *
     * @param array 待排序数组
     * @param left  待排序区间开始下标
     * @param right 待排序区间结束下标
     */
    public static void insertSort_(int[] array,int left,int right) {
        //从left + 1位置开始处理
        for(int i = left+1;i <= right;i++) {

            int tmp = array[i];
            int j = i - 1;
            for(;j >= left;j--) {
                if(tmp < array[j]) {
                    //将比array[i]大的元素往后移
                    array[j + 1]  = array[j];
                }else {
                    //找到了插入位置，结束循环
                    break;
                }
            }

            //将array[i]插入指定的位置,思考：为什么是在j+1位置插入而不是j位置插入元素？
            array[j+1] = tmp;
        }
    }

    /**
     * 简单选择排序
     * @param array 待排序数组
     *  时间复杂度：O(n^2)
     *  空间复杂度：O(1)
     *  稳定性：不稳定
     */
    public static void selectSort(int[] array) {
        //处理空数组
        if(array == null || array.length == 0) {
            return;
        }
        //外层循环代表排序趟数
        for (int i = 0; i < array.length; i++) {
            int index = i;
            int min = array[i];
            //在后 n - i 个元素之中寻找一个最小的元素并记录下标
            for (int j = i; j < array.length; j++) {
                if(array[j] < min) {
                    min = array[j];
                    index = j;
                }
            }
            //交换i所指元素和最小的元素
            swap(array,i,index);
        }
    }

    /**
     * 将一个数组向下调整为大根堆
     * @param array 待处理数组
     * @param parent 根节点
     * @param usedSize 数组有效数据的长度
     */
    public static void siftDown(int[] array,int parent,int usedSize) {
        //向下调整为大根堆
        int child = 2 * parent + 1;
        while (child < usedSize) {
            if(child + 1 < usedSize && array[child] < array[child + 1]) {
                child++;
            }

            if(array[child] > array[parent]) {
                swap(array,parent,child);
                parent = child;
                child = 2 * child + 1;
            }else {
                break;
            }
        }
    }

    /**
     *
     * @param array 将一个创建为大根堆
     */
    public static void createHeap(int[] array) {
        int usedSize = array.length;
        //遍历调整为大根堆

        for(int i = (usedSize - 1 - 1)/2;i >= 0;i--) {
            siftDown(array,i,usedSize);
        }

    }

    /**
     * 堆排序
     * 时间复杂度：O(n*log n)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array 待排序数组
     */
    public static void heapSort(int[] array) {
        //把array数组改造成为大根堆
        int usedSize = array.length;
        createHeap(array);

        //交换堆顶元素和堆底元素
        for (int i = 0;i < array.length;i++) {
            swap(array,0,usedSize - 1);
            usedSize--;
            //将剩下的元素向下调整成为大根堆
            siftDown(array,0,usedSize);
        }

    }
    //快速排序优化：

    /**
     * 思路：对于较小的区间，使用对指定区间的插入排序
     * 划分元素的时候：采用三数取中法 选取枢轴元素
     *
     * @param array 排序数组
     * @param left  开始区间
     * @param right 结束区间
     */
    public static void quick(int[] array,int left,int right) {
        //判断区间是否合法，同时也是递归出口
        if(left > right) {
            return;
        }

        //判断区间大小
        //如果区间大小小于15则使用插入排序
        if(right - left + 1 <= 15) {
            insertSort_(array,left,right);
        }

        //三数取中法，选取一个中位数作为枢轴元素
        int mid = median(array,left,right);
        //将中位数和区间起点元素进行对换
        swap(array,mid,left);
        //以中位数为枢轴元素，对数组指定区间进行划分
        int partition = Partition(array,left,right);

        quick(array,left,partition - 1);
        quick(array,partition + 1,right);
    }

    //父接口
    /**
     * 快速排序
     * @param array
     * 时间复杂度：平均: O（n*log n）  (最坏:有序或者逆序) O(n^2)
     * 空间复杂度：平均： O (log n)    (最坏：有序或者是逆序) O(n^2)
     * 稳定性：不稳定
     */
    public static void quickSort(int[] array) {
          quickSortImpl(array,0,array.length - 1);
    }

    //快速排序优化算法
    public static void quickSort_(int[] array) {
        quick(array,0,array.length - 1);
    }

    //真正的快速排序实现代码
    private static void quickSortImpl(int[] array,int start,int end) {
        //递归出口
        if(start >= end) {
            return;
        }

        int partition = Partition1(array,start,end);
        quickSortImpl(array,start,partition - 1);
        quickSortImpl(array,partition + 1,end);

    }


    //霍尔法实现快速排序划分
    private static int Partition(int[] array,int start,int end) {
        int left = start;
        int right = end;

        //寻找一个分割元素
        int div = array[left];

        while(left < right) {

            while(array[right] > div && left < right) {
                right--;
            }

            while(array[left] <= div && left < right) {
                left++;
            }



            swap(array,left,right);
//            left++;
//            right--;

        }

        //循环结束之后，交换arrary[left]和枢轴元素的值
        int tmp = array[left];
        array[left] = div;
        array[start] = tmp;



        return left;
    }

    //挖坑法实现快速排序划分
    public static int Partition1(int[] array,int start,int end) {
        //选取最开始的元素
        int pivot = array[start];

        int left = start;
        int right = end;

        while(left < right) {

            while(left < right && array[right] > pivot) {
                right--;
            }

            array[left] = array[right];

            while(left < right &&array[left] <= pivot) {
                left++;
            }

            array[right] = array[left];
        }

        //当左右指针相遇的时候，将枢轴元素填入该位置
        array[left] = pivot;

        return left;
    }


    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //三数取中法选取枢轴元素
    private static int median(int[] array,int left,int right) {
        //取中间索引的元素
        int mid = (left + right)/2;

        //在array[left]、array[right]、array[mid]中寻找中位数
        if(array[left] == array[right]) {
            return left;
        }

        //三数取中
        if(array[left] > array[right]) {
            if(array[mid] < array[right]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }else {
            if(array[mid] < array[left]) {
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            } else {
                return mid;
            }
        }

    }

    //快速排序非递归算法
    public static void quickSortNor(int[] array) {
        quickSortNorImpl(array,0,array.length - 1);
    }

    //快速排序非递归算法,实现
    public static void quickSortNorImpl(int[] array,int left,int right) {
          //判断区间是否合法
        if(left > right) {
            return;
        }

        //利用挖坑法
        int mid = Partition1(array,left,right);

        //初始化一个栈
        Stack<Integer> stack = new Stack<>();

        //判断划分之后的子区间长度，如果大于等于2的话则将区间两端的下标压入栈
        if(left < mid - 1) {
            stack.push(mid - 1);
            stack.push(left);
        }

        if(right > mid + 1) {
            stack.push(right);
            stack.push(mid + 1);
        }

        //当栈不为空的时候
        while(!stack.isEmpty()) {
            //获取子区间两端的下标
            int start = stack.pop().intValue();
            int end = stack.pop().intValue();
            //对子区间做划分操作
            int partition = Partition1(array,start,end);

            //判断划分之后的子区间长度,如果大于2，则将子区间两端的下标压入栈
            if(start < partition-1) {
                stack.push(partition - 1);
                stack.push(start);
            }

            //判断划分之后的子区间长度,如果大于2，则将子区间两端的下标压入栈
            if(end > partition + 1) {
                stack.push(end);
                stack.push(partition + 1);
            }
        }

        //当循环结束的时候，数组指定区间已经有序
    }


    //冒泡排序
    public static void bubbleSort(int[] array) {
        //先处理空数组
        if(array == null || array.length == 0) {
            return;
        }

        //设置一个哨兵，记录在一趟排序中是否发生了元素对换
        boolean flag = false;
        //外层循环代表排序趟数
        for (int i = 0; i < array.length; i++) {
            for (int j = 1; j < array.length; j++) {
                 if(array[j] < array[j - 1]) {
                     swap(array,j,j-1);
                     flag = true;
                 }
            }
            //如果在一趟排序中，数组没有发生元素交换，说明数组已经有序
            if(!flag) {
                break;
            }
        }
    }

    //父接口

    /**
     * 归并排序
     * @param array
     * 时间复杂度：O(n*log n)
     * 空间复杂度：O(n)
     * 稳定性：稳定
     */
    public static void mergeSort(int[] array) {
        mergeSortImpl(array,0,array.length - 1);
    }

    //真正实现
    public static void mergeSortImpl(int[] array,int start,int end) {
        //递归出口
        if(start >= end) {
            return;
        }
        //找到中间索引，断开
        int mid = (start + end)/2;

        mergeSortImpl(array,start,mid);
        mergeSortImpl(array,mid + 1,end);

        merge(array,start,end,mid);
    }

    private static void merge(int[] array, int start, int end,int mid) {
           int l1 = start;
           int r1 = mid;
           int l2 = mid+1;
           int r2 = end;

           //创建一个辅助数组
           int[] tmpArray = new int[end - start + 1];

           //辅助指针
           int k = 0;
           //进行归并
           while(l1 <= r1 && l2 <=r2) {
               if(array[l1] <= array[l2]) {
                   tmpArray[k++] = array[l1++];
               }

               if(array[l1] > array[l2]) {
                   tmpArray[k++] = array[l2++];
               }
           }

           //代码走到这里，如果归并段中还有元素剩余，那么剩余的元素一定大于临时数组的最后一个元素

           //处理归并段中有剩余元素的情况
           while(l1 <= r1) {
               tmpArray[k++] = array[l1++];
           }

           while(l2 <= r2) {
               tmpArray[k++] = array[l2++];
           }

           //代码走到这里，临时数组中已经是将两个归并段有序合并之后的序列
           //将临时数组中的元素，写回到待排序的数组中
        for (int i = 0; i < tmpArray.length; i++) {
             array[start + i] = tmpArray[i];
        }
    }
 // 桶排序核心方法
public static void bucketSort(double[] arr) {
    int n = arr.length;
    if (n <= 0) return; // 空数组直接返回


    // 步骤1: 找出数组中的最小值和最大值
    double min = arr[0];
    double max = arr[0];
    for (double num : arr) {
        if (num < min) min = num;
        if (num > max) max = num;
    }

    // 如果所有元素相同，则无需排序
    if (max == min) return;

    // 步骤2: 设置桶的数量（可根据数据分布调整）
    int bucketnum = 5;

    // 步骤3: 创建桶（数量为bucketnum）
    ArrayList<ArrayList<Double>> buckets = new ArrayList<>();
    for (int i = 0; i < bucketnum; i++) {
        buckets.add(new ArrayList<>());
    }

    // 步骤4: 使用新哈希函数分配元素到桶
    for (double num : arr) {
        // 新哈希函数：(元素值 - min) * (bucketnum - 1) / (max - min)
        int bucketIndex = (int) ((num - min) * (bucketnum - 1) / (max - min));
        buckets.get(bucketIndex).add(num);
    }

    // ... 原有排序和合并代码保持不变 ...

    // 步骤3：排序每个非空桶（使用Java内置排序）
    for (ArrayList<Double> bucket : buckets) {
        Collections.sort(bucket); // 底层为归并排序，时间复杂度O(m log m)，m为桶内元素数
    }

    // 步骤4：合并所有桶的元素到原数组
    int index = 0;
    for (ArrayList<Double> bucket : buckets) {
        for (double num : bucket) {
            arr[index++] = num;
        }
    }
}

    //计数排序
    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(d) d = array[max] - array[min]
     * @param array 待排序数组
     */
    public static void countSort(int[] array) {
        //处理空数组
        if(array == null || array.length == 0) {
            return;
        }
        //先查找数组中的最大元素以及最小元素
        int max = array[0];
        int min = array[0];

        for (int i = 1; i < array.length; i++) {
            if(array[i] > max) {
                max = array[i];
            }

            if(array[i] < min) {
                min = array[i];
            }
        }

        //定义一个辅助数组
        int[] tmpArray = new int[max - min + 1];

        //遍历原数组，利用辅助数组进行计数
        //下标映射：
        for (int i = 0; i < array.length; i++) {
             tmpArray[array[i]-min]++;
        }

        int index = 0;
        //遍历辅助数组
        for (int i = 0; i < tmpArray.length; i++) {
            while(tmpArray[i] > 0) {
                array[index] = min + i;
                index++;
                tmpArray[i]--;
            }
        }
    }
}
